package main.sort;

public class RadixSort extends BaseSort {

    public RadixSort(int[] array) {
        super(array);
        this.name = "基数排序";
    }

    /**
     * 先按照个位数从小到大排序，然后十位，百位..
     * <br>
     * [641, 242, 673, 234, 125, 346, 567, 678]<br>
     * [125, 234, 641, 242, 346, 567, 673, 678]<br>
     * [125, 234, 242, 346, 567, 641, 673, 678]
     */
    @Override
    public void sort() {
        int max = getMax();
        int[][] buckets = new int[10][array.length];
        int[] count = new int[10];
        int digit = 1;

        while ((max * 10 / (digit *= 10)) != 0) {
            for (int k : array) {
                int index = k % digit / (digit / 10);
                buckets[index][count[index]++] = k;
            }
            int index = 0;
            for (int i = 0; i < count.length; i++) {
                if (count[i] != 0) {
                    for (int j = 0; j < count[i]; j++) {
                        array[index++] = buckets[i][j];
                    }
                }
                count[i] = 0;
            }
            print();
        }
    }
}
